package leetcode.L236;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    //保存所有节点的父节点
    private Map<Integer, TreeNode> map = new HashMap<>();

    //保存p的祖先
    private Set<Integer> set = new HashSet<>();
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null) {
            return null;
        }
        dfs(root);
        //找到p的所有祖先
        while (p!=null) {
            set.add(p.val);
            p = map.get(p.val);
        }
        while (q != null) {
            if (set.contains(q.val)) {
                return q;
            }
            q = map.get(q.val);
        }
        return null;
    }

    public void dfs(TreeNode root) {
        if (root.left!=null) {
            map.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right!=null) {
            map.put(root.right.val, root);
            dfs(root.right);
        }
    }
}